package week_01;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class LinkedListCycle_ii_142 {
    /**
     * Definition for singly-linked list.
     * class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) {
     * val = x;
     * next = null;
     * }
     * }
     */
    // 首先判断有没有环，如果有环 fast 置为head，slow和fast二者一步一步前进再次相遇的点就是入环节点
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;

                }
                return fast;
            }
        }
        return null;
    }


    public ListNode detectCycle2(ListNode head) {
        Stack stack=new Stack();
        Queue queue=new LinkedList();
        Deque deque=new LinkedList();

        if (head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }

        if (fast == slow) {
            fast = head;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;

            }
            return fast;
        }
        return null;
    }

}
